package seqlist.link.leetcode;

/**
 * @author yuisama
 * @date 2023/03/19 14:52
 * 分隔链表
 **/
public class Num86_PartitionList {
    public ListNode partition(ListNode head, int x) {
        // 1.base case
        if(head == null || head.next == null) {
            return head;
        }
        ListNode smallHead = new ListNode(),bigHead = new ListNode();
        ListNode smallTail = smallHead,bigTail = bigHead;
        // 遍历原链表，将所有值小于x的节点尾插到小链表的尾部
        // >=x 的结点尾插到大链表的尾部
        while (head != null) {
            if (head.val < x) {
                smallTail.next = head;
                smallTail = head;
            }else {
                bigTail.next = head;
                bigTail = head;
            }
            head = head.next;
        }
        // 拼接小链表和大链表
        // 先断掉大链表的尾部节点
        bigTail.next = null;
        smallTail.next = bigHead.next;
        return smallHead.next;
    }
}